package com.zh.note.leetcode.singlestack;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 739. 每日温度
 */
public class LC_739_dailyTemperatures {

    public int[] dailyTemperatures(int[] temperatures) {

        Deque<Integer> stack = new LinkedList<>();
        int[] res = new int[temperatures.length];
        stack.push(0);
        for (int i = 1; i < temperatures.length; i++) {
            if (temperatures[i] < temperatures[stack.peek()]) {   // 当前遍历元素小于栈顶元素
                stack.push(i);
            } else if (temperatures[i] == temperatures[stack.peek()]) {   // 当前遍历的元素等于栈顶元素
                stack.push(i);
            } else {    // 当前遍历元素大于栈顶元素
                while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                    res[stack.peek()] = i - stack.peek();
                    stack.pop();
                }
                stack.push(i);
            }
        }
        return res;
    }
}
